/* 先序与中序遍历分别存在两个一维数组A，B中，试着建立二叉链表 */

#include <iostream>
#include "BiTreefun.h"
using namespace std;

// 根据先序遍历、中序遍历，构建二叉树
BiTree create(char A[], char B[], int L1, int R1, int L2, int R2)
{
  // 创建根结点
  BTNode *root = new BTNode;
  root->data = A[L1];
  
  // 找到中序遍历中，根结点的位置
  int i;
  for (i = L2; B[i] != root->data; i++);
  
  // 如果存在左子树
  if (i > L2)
    root->lchild = create(A, B, L1 + 1, i - L2 + L1, L2, i - 1); // 构建左子树
  else
    root->lchild = NULL; // 左子树为空
  
  // 如果存在右子树
  if (i < R2)
    root->rchild = create(A, B, i - L2 + L1 + 1, R1, i + 1, R2); // 构建右子树
  else
    root->rchild = NULL; // 右子树为空
  
  // 返回根结点
  return root;
}

// 后序遍历
void post(BTNode *T)
{
  // 如果二叉树不为空
  if (T != NULL)
  {
    // 遍历左子树
    post(T->lchild);
    
    // 遍历右子树
    post(T->rchild);
    
    // 打印根结点
    cout << T->data << " ";
  }
}

int main()
{
  // 先序遍历结果
  char A[7] = "abcdef";
  
  // 中序遍历结果
  char B[7] = "cbdaef";
  
  // 建立二叉树
  BTNode *T = create(A, B, 0, 6, 0, 6);
  
  // 后序遍历
  post(T);
  return 0;
}